package com.cjm.algorithm.tree;

import com.cjm.algorithm.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Ti235 {
    public static void main(String[] args) {
        Ti235 ti235 = new Ti235();
//        TreeNode treeNodea = ti235.lowestCommonAncestor(TreeNode.generatorTreeNode(new Integer[]{6,2,8,1,4,7,9,null,null,3,5}), TreeNode.generatorTreeNode(new Integer[]{2}), TreeNode.generatorTreeNode(new Integer[]{8}));
//        TreeNode treeNodeb = ti235.lowestCommonAncestor(TreeNode.generatorTreeNode(new Integer[]{6,2,8,1,4,7,9,null,null,3,5}), TreeNode.generatorTreeNode(new Integer[]{2}), TreeNode.generatorTreeNode(new Integer[]{4}));
//        TreeNode treeNodec = ti235.lowestCommonAncestor(TreeNode.generatorTreeNode(new Integer[]{2,1}), TreeNode.generatorTreeNode(new Integer[]{2}), TreeNode.generatorTreeNode(new Integer[]{1}));
//        TreeNode treeNoded = ti235.lowestCommonAncestor(TreeNode.generatorTreeNode(new Integer[]{2,1,3}), TreeNode.generatorTreeNode(new Integer[]{1}), TreeNode.generatorTreeNode(new Integer[]{3}));
        TreeNode treeNoded = ti235.lowestCommonAncestor(TreeNode.generatorTreeNode(new Integer[]{3,1,4,null,2}), TreeNode.generatorTreeNode(new Integer[]{2}), TreeNode.generatorTreeNode(new Integer[]{3}));
        System.err.println("OK");
    }

    List<Integer> res = new ArrayList<>();
    Map<Integer, TreeNode> map = new HashMap<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        } else {
            return root;
        }
    }
}
